//https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
package codeRandomThoughts.Test19删除链表中的倒数第N个结点;

import codeRandomThoughts.utils.ListNode;

//二刷
public class Solution2 {
    /**
     * 两个思路
     * 1.遍历两遍链表,第一遍求出长度,算出节点在正数第几个,第二遍删除
     * 2.用双指针,一次遍历就可以删除!
     * 快指针先走n步
     * 然后慢指针和快指针一起走
     * 当快指针到达链表末尾
     * 此时慢指针指向链表的倒数第n个节点
     * 但是为了删除,我们要在第n个节点的前一个节点停下,即倒数第n+1个节点停下
     * 我写的是双指针法
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        //快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        //如果直接走到了空结点
        //说明此时要删除的是头节点 直接返回头结点的下一个节点即可
        if (fast == null) {
            return head.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return head;
    }
}
